package com.xs.designpattern;

import java.util.ArrayDeque;
import java.util.NoSuchElementException;

/**
 * Bst迭代器
 * @author xs
 */
public class BstIterator<T extends Comparable<T>> implements Iterator<TreeNode<T>> {
    private final ArrayDeque<TreeNode<T>> pathStack;

    public BstIterator(TreeNode<T> root) {
        pathStack = new ArrayDeque<>();
        pushPathToNextSmallest(root);
    }

    /**
     * 这个 BstIterator 设法使用 O(h) 额外空间，其中 h 是树的高度。它通过在处理自身或右节点之前维护要处理的节点堆栈（首先推送所有左节点）来实现此目的
     *
     * @param node TreeNode 充当我们感兴趣的子树的根
     */
    private void pushPathToNextSmallest(TreeNode<T> node) {
        while (node != null) {
            pathStack.push(node);
            node = node.getLeft();
        }
    }

    /**
     *检查是否存在下一个元素
     *
     * @return 如果此迭代器有“下一个”元素，则为 true
     */
    @Override
    public boolean hasNext() {
        return !pathStack.isEmpty();
    }

    /**
     * 获取下一个元素
     *
     * @return 接下来是树节点。根据给定 BST 的中序遍历的下一个元素
     * @throws NoSuchElementException 如果此迭代器没有下一个元素
     */
    @Override
    public TreeNode<T> next() throws NoSuchElementException {
        if (pathStack.isEmpty()) {
            throw new NoSuchElementException();
        }
        TreeNode<T> next = pathStack.pop();
        pushPathToNextSmallest(next.getRight());
        return next;
    }
}
